// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 包mvs实现了最小的版本选择。
// 请参阅https:
package mvs

import (
	"fmt"
	"sort"
	"sync"

	"cmd/go/internal/par"

	"golang.org/x/mod/module"
)

// Reqs是最小版本选择（MVS）操作的需求图。
// None
// 除特殊版本“无”外，版本字符串是不透明的
// （有关module.Version，请参阅文档）。特别是，MVS没有
// 假设版本字符串是语义版本；取而代之的是Max方法
// 提供对比较操作的访问。
// None
// 同时从多个goroutine调用Reqs上的方法必须是安全的。
// 因为Reqs可以根据需要从网络读取基础图，
// MVS算法将遍历并行化，以重叠网络延迟。
type Reqs interface {
	// Required返回m本身明确需要的模块版本。
	// 调用者不得修改返回的列表。
	Required(m module.Version) ([]module.Version, error)

	// Max返回v1和v2的最大值（它返回v1或v2）。
	// None
	// 对于所有版本v，最大值（v，“无”）必须为v，
	// 对于作为第一个参数传递给MVS函数的目标，
	// Max（target，v）必须是target。
	// None
	// 请注意，v1<v2可以写入最大值（v1，v2）！=v1
	// 类似地，v1<=v2可以写入Max（v1，v2）==v2。
	Max(v1, v2 string) string
}

// UpgradeReqs是一种还可以识别可用升级的Reqs。
type UpgradeReqs interface {
	Reqs

	// 升级返回m的升级版本，
	// 供升级所有操作期间使用。
	// 如果m应保持原样，则升级将返回m。
	// 如果m尚未在构建中使用，则m.Version将为“无”。
	// 更典型的是，m.版本将是所需的版本
	// 通过构建中的其他模块。
	// None
	// 如果给定路径没有可用的模块版本，
	// 升级返回一个非零错误。
	// TODO（rsc）：升级必须能够返回错误，
	// 但是“无最新版本”应该只返回m吗？
	Upgrade(m module.Version) (module.Version, error)
}

// 降级请求是还可以识别可用降级的请求。
type DowngradeReqs interface {
	Reqs

	// Previous返回m.version之前的m.Path版本，
	// 如果不知道此类版本，则为“无”。
	Previous(m module.Version) (module.Version, error)
}

// BuildList返回目标模块的生成列表。
// None
// 目标是模块需求图的根顶点。对于cmd/go，这是
// 通常是主模块，但请注意，此算法不适用于
// 特定于Go：模块路径和版本被视为不透明值。
// None
// reqs描述了模块需求图，并提供了一种不透明的方法
// 用于比较版本。
// None
// BuildList遍历图形并返回一个包含最高值的列表
// 每个访问模块的版本。返回列表的第一个元素是
// 目标本身；reqs.Max要求目标版本比所有版本都高
// 其他版本，因此无法选择其他版本。其余要素
// 列表中的所有项按路径排序。
// None
// 请参阅https:
func BuildList(target module.Version, reqs Reqs) ([]module.Version, error) {
	return buildList(target, reqs, nil)
}

func buildList(target module.Version, reqs Reqs, upgrade func(module.Version) (module.Version, error)) ([]module.Version, error) {
	cmp := func(v1, v2 string) int {
		if reqs.Max(v1, v2) != v1 {
			return -1
		}
		if reqs.Max(v2, v1) != v2 {
			return 1
		}
		return 0
	}

	var (
		mu       sync.Mutex
		g        = NewGraph(cmp, []module.Version{target})
		upgrades = map[module.Version]module.Version{}
		errs     = map[module.Version]error{} // （仅限非零错误）
	)

	// 在需要的情况下并行探索工作图
	// 执行高延迟网络操作。
	var work par.Work
	work.Add(target)
	work.Do(10, func(item interface{}) {
		m := item.(module.Version)

		var required []module.Version
		var err error
		if m.Version != "none" {
			required, err = reqs.Required(m)
		}

		u := m
		if upgrade != nil {
			upgradeTo, upErr := upgrade(m)
			if upErr == nil {
				u = upgradeTo
			} else if err == nil {
				err = upErr
			}
		}

		mu.Lock()
		if err != nil {
			errs[m] = err
		}
		if u != m {
			upgrades[m] = u
			required = append([]module.Version{u}, required...)
		}
		g.Require(m, required)
		mu.Unlock()

		for _, r := range required {
			work.Add(r)
		}
	})

	// 如果出现错误，请查找从目标到目标的最短路径
	// 发生错误的节点，以便我们可以报告有用的错误消息。
	if len(errs) > 0 {
		errPath := g.FindPath(func(m module.Version) bool {
			return errs[m] != nil
		})
		if len(errPath) == 0 {
			panic("internal error: could not reconstruct path to module with error")
		}

		err := errs[errPath[len(errPath)-1]]
		isUpgrade := func(from, to module.Version) bool {
			if u, ok := upgrades[from]; ok {
				return u == to
			}
			return false
		}
		return nil, NewBuildListError(err.(error), errPath, isUpgrade)
	}

	// 最终列表是图表中每个模块的最低版本。
	list := g.BuildList()
	if v := list[0]; v != target {
		// 对于MVS的主客户端modload，target.Version将为“”。
		// “”表示没有版本的主模块。然而，MVS治疗
		// 版本字符串为不透明，因此“”在此处不是特殊值。
		// 见golang.org/issue/31491，golang.org/issue/29773。
		panic(fmt.Sprintf("mistake: chose version %q instead of target %+v", v, target))
	}
	return list, nil
}

// Req返回目标模块的最低要求列表，
// 具有基本中列出的所有模块路径必须
// 出现在返回的列表中。
func Req(target module.Version, base []string, reqs Reqs) ([]module.Version, error) {
	list, err := BuildList(target, reqs)
	if err != nil {
		return nil, err
	}

	// 注意：不并行运行，因为我们假设
	// 该列表来自上一次分页操作
	// 在所有需求中，现在没有I/O重叠。

	// 计算后订单、缓存要求。
	var postorder []module.Version
	reqCache := map[module.Version][]module.Version{}
	reqCache[target] = nil
	var walk func(module.Version) error
	walk = func(m module.Version) error {
		_, ok := reqCache[m]
		if ok {
			return nil
		}
		required, err := reqs.Required(m)
		if err != nil {
			return err
		}
		reqCache[m] = required
		for _, m1 := range required {
			if err := walk(m1); err != nil {
				return err
			}
		}
		postorder = append(postorder, m)
		return nil
	}
	for _, m := range list {
		if err := walk(m); err != nil {
			return nil, err
		}
	}

	// 按相反的后序遍历模块，只添加那些尚未暗示的模块。
	have := map[module.Version]bool{}
	walk = func(m module.Version) error {
		if have[m] {
			return nil
		}
		have[m] = true
		for _, m1 := range reqCache[m] {
			walk(m1)
		}
		return nil
	}
	max := map[string]string{}
	for _, m := range list {
		if v, ok := max[m.Path]; ok {
			max[m.Path] = reqs.Max(m.Version, v)
		} else {
			max[m.Path] = m.Version
		}
	}
	// 首先浏览必须列出的基本模块。
	var min []module.Version
	haveBase := map[string]bool{}
	for _, path := range base {
		if haveBase[path] {
			continue
		}
		m := module.Version{Path: path, Version: max[path]}
		min = append(min, m)
		walk(m)
		haveBase[path] = true
	}
	// 现在倒过来的邮购单带来了其他的东西。
	for i := len(postorder) - 1; i >= 0; i-- {
		m := postorder[i]
		if max[m.Path] != m.Version {
			// 旧版本。
			continue
		}
		if !have[m] {
			min = append(min, m)
			walk(m)
		}
	}
	sort.Slice(min, func(i, j int) bool {
		return min[i].Path < min[j].Path
	})
	return min, nil
}

// UpgradeAll返回目标模块的生成列表
// 其中每个模块都升级到其最新版本。
func UpgradeAll(target module.Version, reqs UpgradeReqs) ([]module.Version, error) {
	return buildList(target, reqs, func(m module.Version) (module.Version, error) {
		if m.Path == target.Path {
			return target, nil
		}

		return reqs.Upgrade(m)
	})
}

// 升级返回目标模块的生成列表
// 其中升级了给定的附加模块。
func Upgrade(target module.Version, reqs UpgradeReqs, upgrade ...module.Version) ([]module.Version, error) {
	list, err := reqs.Required(target)
	if err != nil {
		return nil, err
	}

	pathInList := make(map[string]bool, len(list))
	for _, m := range list {
		pathInList[m.Path] = true
	}
	list = append([]module.Version(nil), list...)

	upgradeTo := make(map[string]string, len(upgrade))
	for _, u := range upgrade {
		if !pathInList[u.Path] {
			list = append(list, module.Version{Path: u.Path, Version: "none"})
		}
		if prev, dup := upgradeTo[u.Path]; dup {
			upgradeTo[u.Path] = reqs.Max(prev, u.Version)
		} else {
			upgradeTo[u.Path] = u.Version
		}
	}

	return buildList(target, &override{target, list, reqs}, func(m module.Version) (module.Version, error) {
		if v, ok := upgradeTo[m.Path]; ok {
			return module.Version{Path: m.Path, Version: v}, nil
		}
		return m, nil
	})
}

// 降级返回目标模块的生成列表
// 其中给定的附加模块降级，
// 可能会覆盖目标的需求。
// None
// 要降级的版本可能无法从最新和
// reqs.Previous，但reqs的方法必须以其他方式处理此类版本
// 正确地
func Downgrade(target module.Version, reqs DowngradeReqs, downgrade ...module.Version) ([]module.Version, error) {
	// 根据https：
	// “为了避免不必要的降级到E1.1，我们还必须增加一个新的
	// E 1.2的要求。我们可以应用算法R来寻找
	// 编写to go.mod的新要求。”
	// None
	// 为了生成这些新需求，我们需要确定版本
	// 对于构建列表中的每个模块-不仅仅是要求（目标）。
	list, err := BuildList(target, reqs)
	if err != nil {
		return nil, err
	}
	list = list[1:] // 清除目标

	max := make(map[string]string)
	for _, r := range list {
		max[r.Path] = r.Version
	}
	for _, d := range downgrade {
		if v, ok := max[d.Path]; !ok || reqs.Max(v, d.Version) != d.Version {
			max[d.Path] = d.Version
		}
	}

	var (
		added    = make(map[module.Version]bool)
		rdeps    = make(map[module.Version][]module.Version)
		excluded = make(map[module.Version]bool)
	)
	var exclude func(module.Version)
	exclude = func(m module.Version) {
		if excluded[m] {
			return
		}
		excluded[m] = true
		for _, p := range rdeps[m] {
			exclude(p)
		}
	}
	var add func(module.Version)
	add = func(m module.Version) {
		if added[m] {
			return
		}
		added[m] = true
		if v, ok := max[m.Path]; ok && reqs.Max(m.Version, v) != v {
			// m将升级现有的依赖项-这不是严格的降级，
			// 而且因为它已经作为依赖项存在，它可能会影响
			// 其他相关包的行为。
			exclude(m)
			return
		}
		list, err := reqs.Required(m)
		if err != nil {
			// 如果无法加载需求，则无法加载go.mod文件。
			// 发生这种情况的原因有很多，但通常
			// 表示模块的旧版本缺少或无效
			// go.mod文件。例如，如果example.com/mod之前发布了v2.0.0
			// 迁移到模块（v2.0.0+不兼容），然后添加有效的go.mod
			// 在v2.0.1中，从v2.0.1降级会导致此错误。
			// None
			// TODO（golang.org/issue/31730，golang.org/issue/30134）：如果
			// 是暂时的（我们无法下载go.mod），从
			// 降级。目前，我们无法判断这是什么样的错误。
			exclude(m)
			return
		}
		for _, r := range list {
			add(r)
			if excluded[r] {
				exclude(m)
				return
			}
			rdeps[r] = append(rdeps[r], m)
		}
	}

	downgraded := make([]module.Version, 0, len(list)+1)
	downgraded = append(downgraded, target)
List:
	for _, r := range list {
		add(r)
		for excluded[r] {
			p, err := reqs.Previous(r)
			if err != nil {
				// 这可能是到达存储库时出现的暂时性错误，
				// 而不是检索到的版本的永久错误。
				// None
				// TODO（golang.org/issue/31730，golang.org/issue/30134）：
				// 根据实际错误解码要执行的操作。
				return nil, err
			}
			// 如果目标版本是伪版本，则可能不是
			// 在使用reqs.Previous迭代以前的版本时包括。
			// 将其插入迭代中的正确位置。
			// 如果v被排除在外，则在下一次迭代中，reqs.Previous应再次返回p。
			if v := max[r.Path]; reqs.Max(v, r.Version) != v && reqs.Max(p.Version, v) != p.Version {
				p.Version = v
			}
			if p.Version == "none" {
				continue List
			}
			add(p)
			r = p
		}
		downgraded = append(downgraded, r)
	}

	// 我们上面计算的降级只会降级到
	// 以前的要求。但是，reqs.Previous省略了一些版本，例如
	// 伪版本和缩回版本-可选择为可传递的
	// 其他模块的要求。
	// None
	// 如果其中一个需求将版本拉回到版本之上
	// 由reqs.Previous标识，然后是该
	// 最初被降级的版本应该不再重要了——特别是我们
	// 不应在模块路径上添加与
	// 更新的模块图甚至需要。
	// None
	// 为了消除这些虚假的依赖关系，我们重新计算构建
	// 列出MVS选择的降级模块的实际版本，
	// 而不是我们最初的降级。
	// （请参阅downhiddenartifact和downhiddencross测试用例）。
	actual, err := BuildList(target, &override{
		target: target,
		list:   downgraded,
		Reqs:   reqs,
	})
	if err != nil {
		return nil, err
	}
	actualVersion := make(map[string]string, len(actual))
	for _, m := range actual {
		actualVersion[m.Path] = m.Version
	}

	downgraded = downgraded[:0]
	for _, m := range list {
		if v, ok := actualVersion[m.Path]; ok {
			downgraded = append(downgraded, module.Version{Path: m.Path, Version: v})
		}
	}

	return BuildList(target, &override{
		target: target,
		list:   downgraded,
		Reqs:   reqs,
	})
}

type override struct {
	target module.Version
	list   []module.Version
	Reqs
}

func (r *override) Required(m module.Version) ([]module.Version, error) {
	if m == r.target {
		return r.list, nil
	}
	return r.Reqs.Required(m)
}
